1. Field of Invention
The field of the invention relates generally to network communication, and more specifically, to networks using a spanning tree algorithm to determine network topology.
2. Discussion of Related Art
Communication networks are generally used to transfer information between computers, referred to in the art as hosts. These hosts may be, for example, general purpose computer systems (e.g., personal computers (PCs), servers, etc.) that communicate data. Generally, a network includes one or more components referred to herein as network forwarding devices that are adapted to receive and forward messages from/to hosts. These network forwarding devices may be in turn coupled to other network forwarding devices in a communication network. Messages sent by hosts (e.g., in the form of data frames, cells, packets, or the like) are received by network forwarding devices and are ultimately forwarded onto a destination host.
Network forwarding devices generally format messages according to one or more network communication protocols, and messages are forwarded according to one or more forwarding protocols. Messages may be, for example, bridged from one network to another according to the IEEE 802.1d standard that defines MAC bridging. The IEEE 802.1d standard also defines a spanning tree protocol that may be used by bridges to eliminate loops in a network.
Loops in a bridged network typically cause problems, such as, for example, messages to be transmitted multiple times over the same interface or cause other communication errors. In general, the spanning tree protocol (STP) allows a distributed network of network forwarding devices (e.g., bridges) to determine a network topology in which loops are eliminated. The ultimate configuration of the network determined by an STP is a tree, with one network path determined as the designed interface to the root bridge. Spanning tree algorithms are well-known in the field of network communication. Spanning tree concepts are discussed with more particularity in the book entitled “Data and Computer Network Communications” by William Stallings, Fourth Edition, 1994, Macmillan Publishing Company, New York, N.Y., herein incorporated by reference by its entirety.
Spanning tree involves communication between one or more network forwarding devices to determine a loop-free topology. The communication determines what is referred to as a root bridge, and determines, at each forwarding device, its minimum path to the root bridge. The bridge having the lowest identifier is chosen to be the root of the spanning tree.
Associated with each port on each network forwarding device is a path cost, which is the cost of transmitting a message (e.g., a frame) onto the network (or other forwarding device) through the respective port. In the simplest case, all path costs can be assigned a value of one (1). Thus the cost of a path in this case is a count of the number of network forwarding devices along the path. Alternatively, costs may be assigned in inverse proportion with respect to data rate, preferred path or corresponding to any other criteria chosen by a network administrator.
Each network forwarding device discovers a first network hop on a minimum-cost path to the root bridge. The port used for that hop is referred to as the root port. For each network forwarding device, the cost of the path to the root bridge with the minimum cost is the root path cost for that network forwarding device.
On each network segment, one network forwarding device is chosen to be the designated bridge. This is the bridge attached to the network segment that provides the minimum cost path to the root bridge. This designated bridge is the only bridge allowed to forward frames to and from the network segment for which the network device is the designated bridge. The port of the designated bridge is the designated port.
In general terms, the spanning tree is constructed in the following manner:    (1) Determine the root bridge    (2) Determine the root port on all other network forwarding devices participating in the spanning tree    (3) Determine the designated port on each network segment, which is the port with the minimum root path cost. In the case of two or more bridges with the same root path cost, then the highest priority bridge is chosen as the designated bridge. If the designated bridge has two or more ports attached to this network segment, then the port having the lowest value of port identifier is chosen.
By this process, when two network segments are directly connected by more than one bridge, all of the bridges but one is eliminated. This process cuts any loops that involve more than one network segment.
The acts above require that network forwarding devices participate in the spanning tree and exchange information. Information is exchanged in the form of bridge protocol data units (BPDUs) as is well-known in the art. A BPDU transmitted by one bridge is addressed and received by all other network forwarding devices connected to the same network segment. Each BPDU includes the following information:    (1) The identifier of the current bridge (the sending bridge) and the port on the bridge    (2) The identifier of the bridge that the current bridge considers to be the root bridge    (3) The root path cost for this bridge
To begin the creation of the spanning tree, each bridge considers themselves to each be the root bridge. Each bridge broadcasts a BPDU on each network segment to which the bridge is attached to assert that they are the root bridge. However, on any given network segment, only one bridge will have the lowest-valued bridge identifier. Over time, as BPDUs are propagated, the identity of the one bridge within the spanning tree will be known to all bridges. The root bridge will broadcast the fact that it is the root bridge to all of the network segments to which the root bridge is attached. This allows each of the bridges on those network segments to determine their respective root port and the fact that they are directly connected to the root bridge.
Each of these bridges in turn broadcasts a BPDU on other network segments to which the respective bridge is attached (except for the network segment attached to the root port), indicating that the bridge is one network hop away from the root bridge. This communication propagates root bridge information throughout the bridged network. Each time that a bridge receives a BPDU, the bridge transmits BPDUs on its ports indicating the identity of the root bridge and the number of network hops to reach the root bridge.
Spanning tree protocol (STP) algorithms are used in a variety of network forwarding devices (switches, routers, etc.) where bridging functions are performed. There are a variety of spanning tree algorithms (e.g., rapid STP, multiple STP, etc.) that may be used in a variety of network types and topologies, and with a variety of network communication protocols. For instance, an STP may be used in conjunction with a Multiprotocol Label Switching (MPLS) network to transmit layer 2 (MAC) frames between dispersed networks connected by an MPLS network. MPLS is defined by the IETF as a protocol for transmitting information using tags. Standards have been proposed to use MPLS networks to form Layer 2 Virtual Private Networks (L2VPN). Further, STP algorithms may be used in Virtual Hierarchical LAN Services (VHLS) networks as proposed by Tenor Networks, Inc., Virtual Private LAN Services (VPLS) as proposed by the IETF, or other network topology types. Further, other core-based networks may use one or more STPs.